//
// Created by Administrator on 2021/4/8.
//

//给定一个二叉树
//
//struct Node {
//    int val;
//    Node *left;
//    Node *right;
//    Node *next;
//}
//        填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
//
//初始状态下，所有next 指针都被设置为 NULL。
//
//
//进阶：
//
//你只能使用常量级额外空间。
//使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

// 与116相比，非完美二叉树
#include <queue>
#include <iostream>

using namespace std;

// Definition for a Node.
class Node {
public:
    int val;
    Node *left;
    Node *right;
    Node *next;

    Node() : val(0), left(nullptr), right(nullptr), next(nullptr) {}

    explicit Node(int _val) : val(_val), left(nullptr), right(nullptr), next(nullptr) {}

    Node(int _val, Node *_left, Node *_right, Node *_next)
            : val(_val), left(_left), right(_right), next(_next) {}
};

vector<vector<int>> levelOrder(Node *root) { //  层次遍历
    vector<vector<int>> ret;
    if (!root) {
        return ret;
    }
    queue<Node *> q;
    q.push(root);
    while (!q.empty()) {
        int currentLevelSize = (int) q.size();
        ret.emplace_back();
        for (int i = 1; i <= currentLevelSize; ++i) {
            auto node = q.front();
            q.pop();
            ret.back().push_back(node->val);
            if (node->next == nullptr) {
                ret.back().push_back(1998); // 1998代替#
            }
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return ret;
}

class Solution {
public:
    Node *connect(Node *root) {
        // 类似层次遍历?
        if (root == nullptr) return root;
        queue<Node *> q;  // 构造一个队列
        q.push(root);
        while (not q.empty()) {
            int n = (int) q.size();
            for (int i = 0; i <= n - 1; i++) {
                Node *node = q.front();
                q.pop();
                if (i < n - 1) // 不是这一层的最后一个，都可以指向队首，即下一个右侧节点
                    node->next = q.front(); // 指向右侧
                if (node->left != nullptr)
                    q.push(node->left); // 左子节点入队
                if (node->right != nullptr)
                    q.push(node->right); // 右子节点入队
            }
        }
        return root;
    }
};
class Solution2 { // 题解 使用已经建立的next指针 链表形式遍历
public:
    void handle(Node* &last, Node* &p, Node* &nextStart) {
        if (last) {
            last->next = p;
        }
        if (!nextStart) {
            nextStart = p;
        }
        last = p;
    }

    Node* connect(Node* root) {
        if (!root) {
            return nullptr;
        }
        Node *start = root;
        while (start) {
            Node *last = nullptr, *nextStart = nullptr;
            for (Node *p = start; p != nullptr; p = p->next) {
                if (p->left) {
                    handle(last, p->left, nextStart);
                }
                if (p->right) {
                    handle(last, p->right, nextStart);
                }
            }
            start = nextStart;
        }
        return root;
    }
};

int main() {
//    输入：root = [1,2,3,4,5,6,7]
//    输出：[1,#,2,3,#,4,5,6,7,#]
    auto t7 = Node(7);
    auto t5 = Node(5);
    auto t4 = Node(4);
    auto t3 = Node(3, nullptr, &t7, nullptr);
    auto t2 = Node(2, &t4, &t5, nullptr);
    auto t1 = Node(1, &t2, &t3, nullptr);
    Solution2 sol;
    sol.connect(&t1);
    vector<vector<int>> ans = levelOrder(&t1);
    for (auto &an : ans) {
        for (int j : an) {
            cout << j << endl;
        }
    }
}